package sort;

/**
 * @description: 堆排序（nlgn） 最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
 * @title: HeapSort
 * @author: zp
 * @date: 2021/11/20 16:25
 */
public class HeapSort extends BaseSort {
    public static void main(String[] args) {
        int count = 8;
        Integer[] ints = new Integer[count];
        for (int i = 0; i < count; i++) {
            ints[i] = (int) (Math.random() * count);
        }
        long start = System.currentTimeMillis();
        sort(ints);
        long end = System.currentTimeMillis();
        System.out.println((end - start));
        System.out.println("===========");
        show(ints);
    }

    public static void sort(Comparable[] a) {
        int length = a.length;
        //构建一个大顶堆 因为是一个二叉树 元素的左右子元素小于本元素
        for (int i = (length / 2 - 1); i >= 0; i--) {
            heapAdjust(a, i, length);
        }
        //构建完成之后 让第一个和最后一个交换位置 因为是大顶堆 第一个元素就是数组中最大的元素 如果交换完成之后去除最后一个元素重新构建大顶堆 如此重复就可以把数组排序
        for (int i = length - 1; i > 0; i--) {
            exch(a, 0, i);
            heapAdjust(a, 0, i);
        }

    }

    public static void heapAdjust(Comparable[] a, int index, int length) {
        //获取本元素的位置
        int max = index;
        //获取本元素左边元素的位置
        int leftNode = index * 2;
        //获取本元素右边元素的位置
        int rightNode = index * 2 + 1;
        //判断下标是否越界 本元素是否大于左边的元素 如果大于交换下标
        if (length > leftNode && less(a[max], a[leftNode])) {
            max = leftNode;
        }
        //判断下标是否越界 本元素是否大于右边的元素 如果大于交换下标
        if (length > rightNode && less(a[max], a[rightNode])) {
            max = rightNode;
        }
        //判断下标是否相同 如果不同交换元素位置 继续递归创建顶堆
        if (!equal(max, index)) {
            exch(a, max, index);
            heapAdjust(a, max, length);
        }

    }
}
